const RedBlackTree = require("../template")

function testRedBlackTreePerformance() {
  console.log(
    "1. 插入性能测试:",
    (() => {
      const rbt = new RedBlackTree()
      const iterations = 1000
      
      const start = performance.now()
      
      for (let i = 0; i < iterations; i++) {
        rbt.insert(i)
      }
      
      const end = performance.now()
      const duration = end - start
      
      return rbt.getSize() === iterations && 
             duration < 1000 && // 应该在1秒内完成
             duration > 0
    })()
  )

  console.log(
    "2. 搜索性能测试:",
    (() => {
      const rbt = new RedBlackTree()
      const iterations = 1000
      
      // 先插入数据
      for (let i = 0; i < iterations; i++) {
        rbt.insert(i)
      }
      
      const start = performance.now()
      
      // 搜索所有数据
      for (let i = 0; i < iterations; i++) {
        rbt.search(i)
      }
      
      const end = performance.now()
      const duration = end - start
      
      return duration < 500 && // 搜索应该很快
             duration > 0
    })()
  )

  console.log(
    "3. 删除性能测试:",
    (() => {
      const rbt = new RedBlackTree()
      const iterations = 500
      
      // 先插入数据
      for (let i = 0; i < iterations; i++) {
        rbt.insert(i)
      }
      
      const start = performance.now()
      
      // 删除一半数据
      for (let i = 0; i < iterations / 2; i++) {
        rbt.delete(i)
      }
      
      const end = performance.now()
      const duration = end - start
      
      return rbt.getSize() === iterations / 2 &&
             duration < 500 &&
             duration > 0
    })()
  )

  console.log(
    "4. 批量操作性能测试:",
    (() => {
      const rbt = new RedBlackTree()
      const batchSize = 500
      
      const start = performance.now()
      
      // 批量插入
      for (let i = 0; i < batchSize; i++) {
        rbt.insert(i)
      }
      
      // 批量搜索
      for (let i = 0; i < batchSize; i++) {
        rbt.search(i)
      }
      
      // 批量删除
      for (let i = 0; i < batchSize / 2; i++) {
        rbt.delete(i)
      }
      
      const end = performance.now()
      const duration = end - start
      
      return rbt.getSize() === batchSize / 2 &&
             duration < 300 &&
             duration > 0
    })()
  )

  console.log(
    "5. 树高度性能测试:",
    (() => {
      const rbt = new RedBlackTree()
      const iterations = 1000
      
      // 插入数据
      for (let i = 0; i < iterations; i++) {
        rbt.insert(i)
      }
      
      const start = performance.now()
      
      // 多次计算树高度
      for (let i = 0; i < 100; i++) {
        rbt.getHeight()
      }
      
      const end = performance.now()
      const duration = end - start
      
      const height = rbt.getHeight()
      const maxHeight = 2 * Math.log2(iterations + 1)
      
      return height <= maxHeight &&
             duration < 100 && // 高度计算应该很快
             duration > 0
    })()
  )

  console.log(
    "6. 中序遍历性能测试:",
    (() => {
      const rbt = new RedBlackTree()
      const iterations = 1000
      
      // 插入数据
      for (let i = 0; i < iterations; i++) {
        rbt.insert(i)
      }
      
      const start = performance.now()
      
      // 多次进行中序遍历
      for (let i = 0; i < 10; i++) {
        rbt.inorder()
      }
      
      const end = performance.now()
      const duration = end - start
      
      const inorder = rbt.inorder()
      
      return inorder.length === iterations &&
             duration < 200 && // 遍历应该很快
             duration > 0
    })()
  )

  console.log(
    "7. 红黑树性质检查性能测试:",
    (() => {
      const rbt = new RedBlackTree()
      const iterations = 1000
      
      // 插入数据
      for (let i = 0; i < iterations; i++) {
        rbt.insert(i)
      }
      
      const start = performance.now()
      
      // 多次检查红黑树性质
      for (let i = 0; i < 100; i++) {
        rbt.isValid()
      }
      
      const end = performance.now()
      const duration = end - start
      
      return rbt.isValid() === true &&
             duration < 200 && // 性质检查应该很快
             duration > 0
    })()
  )

  console.log(
    "8. 大数据量性能测试:",
    (() => {
      const rbt = new RedBlackTree()
      const largeSize = 10000
      
      const start = performance.now()
      
      // 插入大量数据
      for (let i = 0; i < largeSize; i++) {
        rbt.insert(i)
      }
      
      const end = performance.now()
      const duration = end - start
      
      // 验证数据完整性
      let allCorrect = true
      for (let i = 0; i < Math.min(1000, largeSize); i++) { // 抽样检查
        if (rbt.search(i) === null) {
          allCorrect = false
          break
        }
      }
      
      return allCorrect &&
             rbt.getSize() === largeSize &&
             duration < 2000 && // 大数据量应该在2秒内完成
             duration > 0
    })()
  )

  console.log(
    "9. 随机数据性能测试:",
    (() => {
      const rbt = new RedBlackTree()
      const iterations = 1000
      
      // 生成随机数据
      const randomData = Array.from({ length: iterations }, () => 
        Math.floor(Math.random() * 10000)
      )
      
      const start = performance.now()
      
      // 插入随机数据
      randomData.forEach(val => rbt.insert(val))
      
      const end = performance.now()
      const duration = end - start
      
      // 验证数据完整性
      const uniqueData = [...new Set(randomData)]
      let allCorrect = true
      for (let i = 0; i < Math.min(100, uniqueData.length); i++) {
        if (rbt.search(uniqueData[i]) === null) {
          allCorrect = false
          break
        }
      }
      
      return allCorrect &&
             rbt.getSize() === uniqueData.length &&
             duration < 1000 &&
             duration > 0
    })()
  )

  console.log(
    "10. this上下文性能测试:",
    (() => {
      const perfObj = {
        multiplier: 2,
        processPerformance: function(size) {
          const rbt = new RedBlackTree()
          const start = performance.now()
          
          for (let i = 0; i < size; i++) {
            rbt.insert(i)
          }
          
          const end = performance.now()
          return (end - start) * this.multiplier
        }
      }
      
      const result = perfObj.processPerformance(500)
      return result > 0 && result < 1000
    })()
  )

  console.log(
    "11. 复杂对象this绑定性能测试:",
    (() => {
      const perfConfigObj = {
        config: { threshold: 1000 },
        processWithConfig: function(size) {
          const rbt = new RedBlackTree()
          const start = performance.now()
          
          for (let i = 0; i < size; i++) {
            rbt.insert(i)
          }
          
          const end = performance.now()
          return (end - start) < this.config.threshold
        }
      }
      
      return perfConfigObj.processWithConfig(2000) === true
    })()
  )

  console.log(
    "12. 性能一致性测试:",
    (() => {
      const rbt = new RedBlackTree()
      const iterations = 1000
      
      const start1 = performance.now()
      for (let i = 0; i < iterations; i++) {
        rbt.insert(i)
      }
      const end1 = performance.now()
      
      const start2 = performance.now()
      for (let i = 0; i < iterations; i++) {
        rbt.search(i)
      }
      const end2 = performance.now()
      
      const insertTime = end1 - start1
      const searchTime = end2 - start2
      
      return insertTime > 0 &&
             searchTime > 0 &&
             searchTime < insertTime && // 搜索应该比插入快
             rbt.getSize() === iterations
    })()
  )
}

testRedBlackTreePerformance()
